package com.lfg.leetcode.leetcode300;

import java.util.HashMap;
import java.util.Map;


public class No300lengthOfLIS {
    public static void main(String[] args) {
        int ret = lengthOfLIS(new int[]{3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12});
//        int ret = lengthOfLIS(new int[]{1,3,6,7,9,4,10,5,6});
        System.out.println("[" + ret + "]");
    }

    public static int lengthOfLIS(int[] nums) {
        int ret = 0;
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                ret = Math.max(ret, dp[i]);
            }
        }
        return ret;
    }

    public static int lengthOfLIS12(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int length = 0;
        int[] lis = new int[nums.length];
        for (int i : nums) {
            if (length == 0 || i > lis[length - 1]) {
                lis[length++] = i;
                continue;
            }
            int start = 0;
            int end = length - 1;
            int mid = 0;
            while (start < end) {
                mid = (start + end) / 2;
                if (lis[mid] == i) {
                    start = mid;
                    break;
                } else if (lis[mid] >= i) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
            lis[start] = i;
        }

        return length;
    }

    public static int lengthOfLIS2(int[] nums) {
        int cnt = 0;
        if (nums.length == 0) {
            return 0;
        }
        Map<String, Integer> data = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            cnt = Math.max(cnt, dfs(nums, nums[i], i + 1, data));
        }
        return cnt + 1;
    }

    public static int dfs(int[] nums, int num, int index, Map<String, Integer> data) {
        int ret = 0;
        boolean flag = false;
        Integer value = data.get(num + "_" + index);
        if (null != value) {
            return value;
        }
        for (int i = index; i < nums.length; i++) {
            if (nums[i] > num) {
                ret = Math.max(ret, dfs(nums, nums[i], i + 1, data));
                flag = true;
            }
        }
        if (flag) {
            ret++;
        }
        data.put(num + "_" + index, ret);
        return ret;
    }


    public static int lengthOfLIS3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int result = 1;
        for (int i = 1; i < nums.length; i++) {
            int max = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j] && max < dp[j]) max = dp[j];
            }
            dp[i] = max + 1;
            if (result < dp[i]) result = dp[i];
        }
        return result;
    }
}
